[ARC082E]ConvexScore

2020-03-09
#idea #计算几何
Atcoder

题意

如果一个点集$S​$的所有点能连接成为一个凸包（内角严格小于180），那么设所有在凸包边、角、内部的点数为$n​$，$S​$的贡献为$2^{n-|S|}​$

给出点集，求贡献和，$n\leq 200​$

题解

转化问题就会发现，$2^k$的贡献可以视为分给$S\bigcup T$，其中$T$是在凸包但不属于$S$的集合，每个$S\bigcup T$都有1的贡献

进一步，每个面积不为0的点集一定有一个确定的$S$，从而也有确定的$T​$，那么具有1的贡献

问题变成求面积不为0的点集数

调试记录

无

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <algorithm>
#define LL long long
const int maxn = 205;
const LL mo = 998244353;
using namespace std;
int x[maxn], y[maxn], n;
LL ans = 0, pw[maxn];
int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d%d", x + i, y + i);
	pw[0] = 1; for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * 2 % mo; 
	ans = (pw[n] - 1 - n + mo) % mo;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++){
			int tmp = 0;
			for (int k = 1; k <= n; k++){
				if (x[k] >= min(x[i], x[j]) && x[k] <= max(x[i], x[j]) && y[k] >= min(y[i], y[j]) && y[k] <= max(y[i], y[j])){
					if ((y[k] - y[i]) * (x[j] - x[k]) == (x[k] - x[i]) * (y[j] - y[k])) ++tmp;
				}
			}
			ans = (ans - pw[tmp - 2] + mo) % mo;
		}
	printf("%lld\n", ans);
	return 0;
}